package wheel.arithmetic;


/**
 * 基数排序
 *
 * 0-9为基数，从用个位上的数开始进行排序，循环。。。直到用最大位上的数的进行排序则整体排序完成。
 * 桶排序思想的一种，以基数为桶，以位数循环，完成最终的排序。
 */
public class RadixSort {

    public static Integer[] execute(Integer[] arr){
        int len = arr.length;
        /**
         * 获取数组中数值的最大位数（个十百千万等）
         */
        int maxBit = maxBit(arr);
        int[] bucket = new int[10];
        int limit = 1;
        Integer[] temp = new Integer[len];

        for(int i=1; i<=maxBit; i++){

            for(int j=0; j<10; j++)
                bucket[j] = 0;

            for(Integer e : arr){
                int radix = (e/limit)%10;
                bucket[radix]++;
            }


            for(int j=1; j<10; j++){
                bucket[j] = bucket[j-1] + bucket[j];
            }

            for(int j=len-1; j>=0; j--){
                int radix = (arr[j]/limit)%10;
                temp[bucket[radix] - 1] = arr[j];
                bucket[radix]--;
            }



            System.arraycopy(temp, 0, arr, 0, len);


            limit*=10;

        }
        return arr;
    }

    static Integer maxBit(Integer[] arr){
        int max = 1;
        int limit = 10;
        for(int e : arr){
            if(e>=limit){
                max++;
                limit*=10;
            }
        }
        return max;
    }

    //耗时: 31ms 47ms 31ms 十万个
    //耗时: 1148ms 1050ms 1181ms 一百万个
    //耗时: 13506ms 14179ms 13817ms 一千万个
    //耗时: 196562ms 一亿个

}
